#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#include<time.h>
#include<windows.h>

#define BASE 10
#define MAX 90000

void printArr(char **arr, int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%s\t", arr[i]);
    }
}

void swap(char **arr, int start, int end) {
    while(start < end) {
        char *temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        start++;
        end--;
    }
}

void radixSort(char **arr, int start, int end, int negativeFlag) {
    int num = end - start;
    int i, exp = 1;
    char *temp[num];
    char *max = arr[start];

    for (i = start + 1; i <= end; i++) {
        int maxLen = strlen(max);
        int eleLen = strlen(arr[i]);

        if (maxLen < eleLen) {
            max = arr[i];
        } else if (maxLen == eleLen) {
            if (strcmp(arr[i], max) > 0) {
                max = arr[i];
            }
        }
    }

    int len = strlen(max);

    while (((len - exp) >= 0 && negativeFlag == 0) || ((len - exp) > 0 && negativeFlag == 1)) {
        int bucket[BASE] = {0};

        for (i = start; i <= end; i++) {
            int eleLen = strlen(arr[i]);
            int eleIndex = eleLen - exp;

            int bucketIndex = 0;

            if ((eleIndex < 0 && negativeFlag == 0) || (eleIndex <=0 && negativeFlag == 1)) {
                bucketIndex = 0;
            } else {
                bucketIndex = arr[i][eleIndex] - '0';
            }

            bucket[bucketIndex]++;
        }

        for (i = 1; i < BASE; i++) {
            bucket[i] += bucket[i - 1];
        }

        for (i = end; i >= start; i--) {
            int eleLen = strlen(arr[i]);
            int eleIndex = eleLen - exp;
            int bucketIndex = 0;

            if ((eleIndex < 0 && negativeFlag == 0) || (eleIndex <=0 && negativeFlag == 1)) {
                bucketIndex = 0;
            } else {
                bucketIndex = arr[i][eleIndex] - '0';
            }

            temp[--bucket[bucketIndex]] = arr[i];
        }

        for (i = 0; i <= num; i++) {
            arr[start + i] = temp[i];
        }

        exp++;
    }

    if (negativeFlag == 1) {
        swap(arr, start, end);
    }
}

void sort(char **arr, int n) {
    int i = 0, j = n - 1;
    int negativeFlag = 0;

    while(i < j) {
        while(i < j && strcmp(arr[i], "0") < 0) {
            i++;
            if (negativeFlag == 0) {
                negativeFlag = 1;
            }
        }
        
        while(i < j && strcmp(arr[j], "0") >= 0) {
            j--;
        }

        if (i < j) {
            swap(arr, i, j);
        }
    }

    if (negativeFlag == 1) {
        if (i == n - 1) { // all negative
            radixSort(arr, 0, n-1, negativeFlag);
        } else {
            radixSort(arr, 0, i-1, negativeFlag);
            radixSort(arr, i, n - 1, 0);
        }
    } else {
        radixSort(arr, 0, n - 1, 0);
    }
}

char* joinStr(char *s1, char *s2) {
    char *result = malloc(strlen(s1)+strlen(s2)+1);
    if (result == NULL) exit (1);

    strcpy(result, s1);
    strcat(result, s2);

    return result;
}

void generateArr(char **arr, int len) {
    int temp;
    time_t t;
    /* 初始化随机数发生器 */
    srand((unsigned) time(&t));
    char nums[10] = "0123456789";

    for (int i = 0; i < len; i++) {
        int num = rand() % 9 + 1;
        char temp[num];

        for (int j = 0; j < num; j++) {
            int r = rand() % 10;
            if (j == 0 && r == 0) {
                r = 1;
            }
            temp[j] = nums[r]; 
        }
        temp[num] = '\0';

        int odd = rand() % 2;
        if (odd == 0) {
            arr[i] = joinStr("-", temp);
        } else {
            arr[i] = joinStr("", temp);
        }
    }
}

int main(int argc, char const *argv[])
{
    char *arr[MAX] = {};
    int n = MAX;

    long long start, end;

    generateArr(arr, n);

    start = GetTickCount();
    sort(arr, n);
    end = GetTickCount();

    printf("\nstart=%lld\n", start);
    printf("end=%lld\n", end);
    printf("diffTime=%lld\n", end - start);

    // printArr(arr, n);

    return 0;
}
